import collections
class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        if not amount:
            return 0
        now_stack = collections.defaultdict(int)
        now_stack[0] = 1
        n = len(coins)
        index = 0
        total = 0
        while index < n:
            next_stack = collections.defaultdict(int)
            for key in now_stack:
                next_stack[key] += now_stack[key]
                k = 1
                value = key + k * coins[index]
                while value < amount:
                    next_stack[value] += now_stack[key]
                    k += 1
                    value = key + k * coins[index]
                if value == amount:
                    total += now_stack[key]
            now_stack = next_stack
            index += 1
        return total


data = Solution()
amount = 5
coins = [1, 2, 5]
print(data.change(amount, coins))
